package algorithm.middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Merge56 {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(b[1], a[1]);
            }
            return Integer.compare(a[0], b[0]);
        });
        List<int[]> res = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int l = intervals[i][0];
            int r = intervals[i][1];
            int move = i + 1;
            while (move < intervals.length && intervals[move][0] <= r) {
                if (intervals[move][1] >= r) {
                    r = intervals[move][1];
                }
                move++;
            }
            res.add(new int[]{l, r});
            i = move - 1;
        }
        int[][] ints = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            ints[i] = res.get(i);
        }
        return ints;
    }

}
